Corelab Seminar
2019-2020
Manolis Vlatakis
Smoothed complexity of local Max-Cut and binary Max-CSP
Abstract.
This work provides insights into the inner-workings of some of the most widely used local search methods. A recurring phenomenon in local search algorithms is that they are usually efficient in practice but the theory of worst-case analysis indicates the opposite — due to some delicate pathological instances that one may never encounter in practice, the algorithm would be characterized as an exponential running time method. In order to bridge theory and practice, a smoothed complexity framework has been introduced, a hybrid complexity model between the pessimistic worst-case analysis and the optimistic average-case analysis.
This work analyzes the MaxCut problem, one of the famous 21-Karp NP-complete (''hard'') problems. Given a weighted undirected graph, the MaxCut problem seeks to partition the vertices of the graph into two sets such that the sum of the weights of the edges that join the two sets is maximized. Its applications come from diverse areas including layout of electronic circuitry, social networks and statistical physics.
We improved the smoothed complexity of the local search methods for the Max-Cut problem. to n
√ log n
running time. The result is based on an analysis of long sequences of local changes (flips), which shows that it is very unlikely for every flip in a long sequence to incur a positive but small improvement in the cut weight. We also extend the same upper bound on the smoothed complexity of FLIP to all binary Maximum Constraint Satisfaction Problems.all binary Maximum Constraint Satisfaction Problems.
This work will appear in STOC 2020 and can be found online
here.